package cn.connorma.example.bitmap_example;

/**
 * 一个简单的bitmap实现，使用 (2^31 - 8)bit 大小的空间支持大规模整数的查找（可以很容易扩展出排序和统计）
 * 可以指定起始值和结束值以切换允许的数据范围，并且可以指定单个存储单元占用的bit位数，以支持扩展更多数据状态
 *
 * @author matian
 * @date 2022-12-11 10:10:37
 */
public class CustomBitmap {

    // Integer.MAX_VALUE = 2^31 - 1 = 21 4748 3647
    private final int MAX_LENGTH = Integer.MAX_VALUE - 8;
    private final byte[] bitmap = new byte[MAX_LENGTH];

    /**
     * 每个元素状态记录时占用的bit位数，占用的bit位数越多那么可以表示的状态越多，但是bitmap可容纳的数据条数相应减少
     * 0 < span < 8，达到8时相当于直接使用byte类型，使用bitmap无意义
     * 约定span是2的幂，方便处理，否则会出现一个num的state存储跨字节的情况
     */
    private final int span;

    /**
     * bitmap起始bit对应的索引值，bitmap支持的数据索引范围为 >= start
     */
    private final int start;
    /**
     * 根据start和span计算出的bitmap支持的最大索引值，数据索引范围为 < end
     */
    private final int end;
    /**
     * 指定span下，支持的状态字段的最大值 < (2^span)
     */
    private final int maxStateVal;

    public CustomBitmap() {
        this(0, 1);
    }

    public CustomBitmap(int start, int span) {
        this.start = start;

        if (span <= 0 || span >= 8 || ((span & -span) != span) && span != 1) {
            throw new IllegalStateException("span should between 0(inclusive) to 8(exclusive), and be 1 or a power of 2.");
        }
        this.span = span;

        if (Integer.MAX_VALUE - MAX_LENGTH / span <= start) {
            this.end = MAX_LENGTH;
        } else {
            this.end = start + MAX_LENGTH / span;
        }

        this.maxStateVal = (int) Math.pow(2, span);
    }

    public int getSpan() {
        return span;
    }

    public int getStart() {
        return start;
    }

    public int getEnd() {
        return end;
    }

    public int getMaxStateVal() {
        return maxStateVal;
    }

    /**
     * 记录数据的状态值
     *
     * @param num   数据
     * @param state 状态值，支持的范围为: [0, 2^span)
     */
    public void set(int num, int state) {
        if (num < start) {
            throw new IllegalArgumentException("bitmap support num should be greater or equals to " + start);
        }
        if (num >= end) {
            throw new IllegalArgumentException("bitmap support num should be less to " + end);
        }
        if (state < 0 || state >= maxStateVal) {
            throw new IllegalArgumentException("bitmap with span " + span + " support state between [0," + maxStateVal + ")");
        }

        // num对应的bit的索引
        int bitIndex = (num - start) * span;
        // bit所在的byte元素
        int byteIndex = bitIndex / 8;

        // byte内此num对应的span起始位置偏移量
        int bitOffset = bitIndex - byteIndex * 8;

        byte oldByteVal = bitmap[byteIndex];

        // 将num对应位置的bit全部置为0
        // 鄙人不擅长位运算，直接for一下依次置0
        for (int i = 0; i < span; i++) {
            int bitAddr = i + bitOffset;
            byte mask = (byte) (0x01 << bitAddr);
            mask = (byte) ~mask;
            oldByteVal = (byte) (oldByteVal & mask);
        }

        byte stateVal = (byte) (state << bitOffset);
        byte newByteVal = (byte) (stateVal | oldByteVal);

        bitmap[byteIndex] = newByteVal;
    }

    /**
     * 查找某个数据记录的状态，查找不到时返回0
     *
     * @return 状态值
     */
    public int get(int num) {
        if (num < start) {
            return 0;
        }
        if (num > end) {
            return 0;
        }

        // num对应的bit的索引
        int bitIndex = (num - start) * span;
        // bit所在的byte元素
        int byteIndex = bitIndex / 8;

        // byte内此num对应的span起始位置偏移量
        int bitOffset = bitIndex - byteIndex * 8;

        // 将v在num的span位置的bit全部置为1，其他为0
        // 鄙人不擅长位运算，直接for一下依次置1
        byte v = 0;
        for (int i = 0; i < span; i++) {
            int bitAddr = i + bitOffset;
            byte mask = (byte) (0x01 << bitAddr);
            v = (byte) (v | mask);
        }

        byte val = (byte) (v & bitmap[byteIndex]);
        val = (byte) (val >>> bitOffset);

        // 构造mask，在val移位后的span位置bit全部置为1，其他为0
        v = 0;
        for (int i = 0; i < span; i++) {
            byte mask = (byte) (0x01 << i);
            v = (byte) (v | mask);
        }

        return val & v;
    }

}
